public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;

        //增加虚拟结点
        int[][] ret = new int[m + 1][n + 1];

        //初始化结点
        ret[0][1] = 1;

        //遍历矩阵
        for (int i = 1; i < m + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                if (obstacleGrid[i - 1][j - 1] == 1) {
                    ret[i][j] = 0;
                } else {
                    ret[i][j] = ret[i - 1][j] + ret[i][j - 1];
                }
                // ret[i][j] = ret[i - 1][j] + ret[i][j - 1];
            }
        }
        return ret[m][n];
    }
}
